"""P14 14.基础提升 树形dp套路、二叉树的Morris遍历、位图解决范围数组问题"""

"""
树形dp套路：

树形dp套路使用的前提：
如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头节点的子树在S规则下
的每一个答案，并且最终答案一定在其中。

树形dp套路第一步：
以某个节点X为头节点的子树中，分析答案有那些可能性，并且这种分析是以X的
左子树、X的右子树和X整棵树的角度来考虑可能性的

树形dp套路第二步：
根据第一步的可能性分析，列出所有需要的信息

树形dp套路第三步：
合并第二步的信息，对左子树和右子树提出同样的要求，并写出信息结构

树形dp套路第四步：
设计递归函数，递归函数是处理以X为头节点的情况下的答案。
包括设计递归的base case，默认直接得到左子树和右子树的所有信息，以及
把可能性做整合，并且要返回第三步的信息结构
"""

"""
二叉树节点间的最大距离问题：
从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点B时，
路径上的节点个数叫做A到B的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的
最大距离

最大距离求解思路：
1、根节点不参与：最大距离来自左子树或者右子树的最大距离
2、根节点参与：最大距离等于左子树的高度加上右子树的高度，再加一
以上条件下的最大距离中取最大值
"""


class TreeNode:
    """二叉树节点"""

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def max_distance(head: TreeNode) -> tuple:
    if not head:
        return 0, 0
    left_info = max_distance(head.left)
    right_info = max_distance(head.right)
    distance = max(left_info[0], right_info[0],
                   left_info[1] + right_info[1] + 1)
    height = max(left_info[1], right_info[1])
    return distance, height


"""
派对的最大快乐值：
公司的每个员工都符合Employee类的描述。整个公司的人员结构可以看作是一棵
标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工
都有唯一的直接上级。叶节点是没有任何下属的基层员工(subordinates列表为空)，
除基层员工外，每个员工都有一个或多个直接下级。

这个公司现在要办party,你可以决定哪些员工来，哪些员工不来。但是要遵循如下规则。
1、如果某个员工来了，那么这个员工的所有自接下级都不能来
2、派对的整体快乐值是所有到场员工快乐值的累加
3、你的目标是上派对的整体快乐值尽量大

给定一棵多叉树的头节点head,请返回派对的最大快乐值。

派对的最大快乐值求解思路：
1、头结点head参与：最大快乐值 = head.happy + head的每个子树头结点不参与的最大快乐值
2、头结点head不参与：最大快乐值 = head的每个子树的最大快乐值之和
"""


class Employee:
    """公司员工"""

    def __init__(self, happy: int):
        self.happy = happy
        self.subordinates = list()


def max_happy(head: Employee) -> tuple:
    if not head.subordinates:
        return head.happy, 0
    with_happy = head.happy
    without_happy = 0
    for i in head.subordinates:
        info = max_happy(i)
        with_happy += info[1]
        without_happy += max(info)
    return with_happy, without_happy


"""
Morris遍历：
一种遍历二叉树的方式，并且时间复杂度O(N),额外空间复杂度O(1)
通过利用原树中大量空闲指针的方式，达到节省空间的目的

Morris遍历细节
假设来到当前节点cur,开始时cur来到头节点位置
1)如果cur没有左孩子，cur向右移动(cur=cur.right)
2)如果cur有左孩子，找到左子树上最右的节点mostRight:
    a.如果mostRight的右指针指向空，让其指向cur,然后cur向左移动(cur=cur.let)
    b.如果mostRight的右指针指向cur,让其指向null,然后cur向右移动(cur=cur.right)
3)cur为空时遍历停止

如果严禁修改二叉树，那么Morris遍历就无法使用
Morris遍历最多经过头节点两次
"""


def morris(head: TreeNode):
    if not head:
        return
    cur = head
    while cur:
        most_right = cur.left
        if most_right:  # 如果有左子树
            while most_right.right and most_right.right != cur:
                most_right = most_right.right
            # most_right变成了cur左子树上最右的节点
            if not most_right.right:
                most_right.right = cur
                cur = cur.left
                continue
            else:  # most_right.right == cur
                most_right.right = None
        cur = cur.right


"""
Morris的先序遍历：
1、如果一个节点只能到达一次，直接打印
2、如果一个节点可以到达两次，第一次时打印
"""


def morris_preorder(head: TreeNode):
    if not head:
        return
    cur = head
    while cur:
        most_right = cur.left
        if most_right:
            while most_right.right and most_right.right != cur:
                most_right = most_right.right
            # most_right变成了cur左子树上最右的节点
            if not most_right.right:  # 可以到达两次的节点，第一次到达
                print(cur.value)
                most_right.right = cur
                cur = cur.left
                continue
            else:  # most_right.right == cur
                most_right.right = None
        else:  # 只到达一次的节点
            print(cur.value)
        cur = cur.right


"""
Morris的中序遍历：
1、如果一个节点只能到达一次，直接打印
2、如果一个节点可以到达两次，第二次时打印
"""


def morris_intermediate(head: TreeNode):
    if not head:
        return
    cur = head
    while cur:
        most_right = cur.left
        if most_right:
            while most_right.right and most_right.right != cur:
                most_right = most_right.right
            # most_right变成了cur左子树上最右的节点
            if not most_right.right:
                most_right.right = cur
                cur = cur.left
                continue
            else:  # most_right.right == cur
                most_right.right = None
        print(cur.value)
        cur = cur.right


"""
Morris的后序遍历：
对于可以到达两次的节点，在第二次到达的时候，逆序打印自己的左子树的右边界
最后单独逆序打印整棵树的右边界
"""


def reverse_edge(node: TreeNode) -> TreeNode:
    """逆序node整棵树的右边界"""
    before_node = None
    while node:
        next_node = node.right
        node.right = before_node
        before_node = node
        node = next_node
    return before_node


def print_edge(node: TreeNode):
    """打印node整棵树的右边界"""
    reverse_node = reverse_edge(node)
    cur = reverse_node
    while cur:
        print(cur.value)
        cur = cur.right
    reverse_edge(reverse_node)


def morris_post_order(head: TreeNode):
    if not head:
        return
    cur = head
    while cur:
        most_right = cur.left
        if most_right:
            while most_right.right and most_right.right != cur:
                most_right = most_right.right
            # most_right变成了cur左子树上最右的节点
            if not most_right.right:
                most_right.right = cur
                cur = cur.left
                continue
            else:  # most_right.right == cur
                most_right.right = None
                print_edge(cur.left)
        cur = cur.right
    print_edge(head)


"""
判断一棵树是否为搜索二叉树，即中序遍历为升序
"""


def is_search_tree(head: TreeNode) -> bool:
    if not head:
        return True
    cur, before_value = head, float("-inf")
    while cur:
        most_right = cur.left
        if most_right:
            while most_right.right and most_right.right != cur:
                most_right = most_right.right
            # most_right变成了cur左子树上最右的节点
            if not most_right.right:
                most_right.right = cur
                cur = cur.left
                continue
            else:  # most_right.right == cur
                most_right.right = None
        if cur.value <= before_value:
            return False
        before_value = cur.value
        cur = cur.right
    return True


"""
如果需要做第三次信息的强整合，以上树形dp套路为最优解，否则Morris遍历为最优解
"""

"""
32位无符号整数的范围是0 ~ 4,294,967,295，现在有一个正好包含40亿个无符号整数
的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，
怎么找到所有未出现过的数？
【进阶】
内存限制为10MB,但是只用找到一个没出现过的数即可

解题思路1：
根据允许的内存大小，来确定词频数组的大小，而词频最小的组一定有没出现过的数，
再通过bit数组的方式筛选出最小词频组中没出现过的数

解题思路2：
以整数范围进行二分，确认两个词频组，再继续对较小词频组的范围进行二分处理，
直到范围到达一个整数为止
"""